package 树.Trie;

public class 键值映射_677 {
    class MapSum {

        int sum; // 前缀对应的和
        MapSum[] children; //子节点
        Integer val; // key对应的val，null表示还没有key


        /**
         * Initialize your data structure here.
         */


        public MapSum() {
            children = new MapSum[26];
            sum = 0;
            val = null;
        }


        // 获取指定key对应的val，key不存在返回null
        public Integer getVal(String key) {
            MapSum cur = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该key在trie中。
                    return null;//没有就返回null
                }
                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            return cur.val;//存在就返回该节点的值
        }

        // 插入(key，val)，更新每个节点val和sum
        public void insert(String key, int val) {
            Integer old = getVal(key);
            if (old == null) { // 不存在key
                old = 0;
            }
            MapSum cur = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该字符在trie中。
                    cur.children[c - 'a'] = new MapSum();//没有就新建一个
                }

                cur.sum = cur.sum - old + val; // 遍历过程中更新当前节点的sum值，中间节点不更新val
                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            cur.sum = cur.sum - old + val; // 更新最后一个节点的sum值
            cur.val = val; // 更新最后一个节点的val值
        }


        // 查找前缀对应的sum
        public int sum(String prefix) {
            MapSum cur = this;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有key在trie中。
                    return 0;//没有就返回0
                }

                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            return cur.sum; //有就返回这个sum
        }
    }

}
